﻿//class Solution
//{
//public:
//	int minCut(string s)
//	{
//		int n = s.size();
//		vector<vector<bool>> isPal(n, vector<bool>(n)); // 统计所有⼦串是否是回⽂串
//		for (int i = n - 1; i >= 0; i--)
//			for (int j = i; j < n; j++)
//				isPal[i][j] = s[i] == s[j] ? (i + 1 < j ? isPal[i + 1][j - 1] :
//					vector<int> dp(n, INT_MAX);
//		for (int i = 0; i < n; i++)
//		{
//			if (isPal[0][i]) dp[i] = 0;
//			else
//			{
//				for (int j = 1; j <= i; j++)
//					if (isPal[j][i])
//						dp[i] = min(dp[i], dp[j - 1] + 1);
//			}
//		}
//		return dp[n - 1];
//	}
//};